/*
 * @lc app=leetcode.cn id=67 lang=cpp
 *
 * [67] 二进制求和
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    string addBinary(string a, string b) {
        int left = a.size() - 1;
        int right = b.size() - 1;
        int flag = 0;
        string result = "";

        while (left >= 0 || right >= 0 || flag > 0) {
            // 从两个字符串中各取出一个字符并转换为数字
            int leftValue = (left >= 0) ? a[left] - '0' : 0;
            int rightValue = (right >= 0) ? b[right] - '0' : 0;
            left--;
            right--;

            // 计算两个字符串和进位符号
            int tmpValue = leftValue + rightValue + flag;
            
            // 将计算结果转化为相应的数字
            if (tmpValue == 3) {
                result.push_back('1');
                flag = 1;
            } else if (tmpValue == 2) {
                result.push_back('0');
                flag = 1;
            } else if (tmpValue == 1) {
                result.push_back('1');
                flag = 0;
            } else {
                result.push_back('0');
                flag = 0;
            }
        }
        
        // 将结果字符串逆序
        reverse(result.begin(), result.end());

        return result;
    }
};
// @lc code=end

